import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: CC20 分割回文串
 * <a href="https://www.nowcoder.com/practice/f983806a2ecb4106a17a365a642a9632?tpId=46&tPage=1&rp=1&ru=%2Fta%2Fleetcode&qru=%2Fta%2Fleetcode%2Fquestion-ranking&difficulty=&judgeStatus=&tags=&title=&sourceUrl=&gioEnter=menu%22">...</a>
 * User: DELL
 * Date: 2023-05-10
 * Time: 15:10
 */

//  大佬的总结:
//  如要输出所有的解,往往深度优先搜索
//  如要求出解的个数或最优解,往往动态规划
public class Solution {
    /**
     * 解法一: 深度优先搜索 == 递归 + 回溯
     * 总体思想将需要分割的字符串分成“前后”两部分，先对“前半”字符串进行判断，
     * 若是回文字符串，则采用递归思想对“后半”字符串进行分割。若“前半”字符串
     * 不是回文字符串，则增加其长度，继续判断。直至所有情况均被考虑。
     */
    public ArrayList<ArrayList<String>> partition (String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<>();
        //检验合法性
        if (s == null || s.length() == 0) {
            return res;
        }
        LinkedList<String> temp = new LinkedList<>();
        recursion(res,temp,s,0);
        return res;
    }

    /**
     * 深度优先搜索每个可能的分割结果
     * @param res        记录分割结果的链表
     * @param temp       临时记录每个分割结果的链表
     * @param s          原字符串
     * @param index      字串第一个字符在 s 字符串中的下标
     */
    private static void recursion(ArrayList<ArrayList<String>> res, LinkedList<String> temp, String s, int index) {
        //递归结束条件
        if (index == s.length()) {
            //这里要记得必须加入的是 new 出来的
            res.add(new ArrayList<>(temp));
        }
        //遍历每一种结果
        for (int i = index; i < s.length(); i++) {
            if (isPal(s,index,i)) {
                temp.add(s.substring(index,i+1));
                recursion(res,temp,s,i+1);
                //回溯
                //这里需要使用 removeLast方法,
                //因为 remove 默认是 removeFirst
                temp.removeLast();
            }
        }
    }

    private static boolean isPal(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}